<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 定义二叉搜索树节点
      function createNode(value) {
        return {
          value: value,
          left: null,
          right: null,
        };
      }

      // 插入节点
      function insert(root, value) {
        if (root === null) {
          return createNode(value);
        }
        if (value < root.value) {
          root.left = insert(root.left, value);
        } else if (value > root.value) {
          root.right = insert(root.right, value);
        }

        return root;
      }

      // 查找节点
      function search(root, value) {
        if (root === null || root.value === value) {
          return root;
        }

        if (value < root.value) {
          return search(root.left, value);
        } else {
          return search(root.right, value);
        }
      }

      // 删除节点
      function remove(root, value) {
        if (root === null) {
          return root;
        }

        if (value < root.value) {
          root.left = remove(root.left, value);
        } else if (value > root.value) {
          root.right = remove(root.right, value);
        } else {
          // 找到节点
          if (root.left === null) {
            return root.right;
          } else if (root.right === null) {
            return root.left;
          }

          const minLargerNode = findMin(root.right);
          root.value = minLargerNode.value;
          root.right = remove(root.right, minLargerNode.value);
        }

        return root;
      }

      // 查找树中最小的节点
      function findMin(root) {
        while (root.left !== null) {
          root = root.left;
        }
        return root;
      }

      // 中序遍历
      function inorderTraversal(root, result = []) {
        if (root !== null) {
          inorderTraversal(root.left, result);
          result.push(root.value);
          inorderTraversal(root.right, result);
        }
        return result;
      }

      // 示例使用
      const bst = insert(insert(insert(null, 50), 30), 70);
      insert(bst, 20);
      insert(bst, 40);
      insert(bst, 60);
      insert(bst, 80);

      console.log("中序遍历结果:", inorderTraversal(bst)); // 输出: [20,30,40,50,60,70,80]

      const searchResult = search(bst, 20);
      console.log("搜索结果:", searchResult ? searchResult.value : "未找到"); // 输出:20remove(bst,20);
      console.log("删除后中序遍历结果:", inorderTraversal(bst)); // 输出: [30,40,50,60,70,80]
    </script>
  </body>
</html>
